{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Verify Preorder Sequence in Binary Search Tree"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #stack #tree #binary-search-tree #recursion #binary-tree #monotonic-stack"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #栈 #树 #二叉搜索树 #递归 #二叉树 #单调栈"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: verifyPreorder"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #验证前序遍历序列二叉搜索树"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给定一个&nbsp;<b>无重复元素</b>&nbsp;的整数数组&nbsp;<code>preorder</code>&nbsp;，&nbsp;<em>如果它是以二叉搜索树的<strong>先序遍历</strong>排列</em><em>&nbsp;</em>，返回 <code>true</code> 。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<p><img src=\"https://assets.leetcode.com/uploads/2021/03/12/preorder-tree.jpg\" /></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入: </strong>preorder = [5,2,1,3,6]\n",
    "<strong>输出: </strong>true</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入: </strong>preorder = [5,2,6,1,3]\n",
    "<strong>输出: </strong>false</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示:</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= preorder.length &lt;= 10<sup>4</sup></code></li>\n",
    "\t<li><code>1 &lt;= preorder[i] &lt;= 10<sup>4</sup></code></li>\n",
    "\t<li><code>preorder</code>&nbsp;中&nbsp;<strong>无重复元素</strong></li>\n",
    "</ul>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>进阶：</strong>您能否使用恒定的空间复杂度来完成此题？</p>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [verify-preorder-sequence-in-binary-search-tree](https://leetcode.cn/problems/verify-preorder-sequence-in-binary-search-tree/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [verify-preorder-sequence-in-binary-search-tree](https://leetcode.cn/problems/verify-preorder-sequence-in-binary-search-tree/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[5,2,1,3,6]', '[5,2,6,1,3]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def verifyPreorder(self, preorder: List[int]) -> bool:\n",
    "        s = []\n",
    "        m = float('-inf')\n",
    "        for v in preorder:\n",
    "            if v < m:\n",
    "                return False\n",
    "            while s and s[-1] < v:\n",
    "                t = s.pop()\n",
    "                m = max(m, t)\n",
    "            s.append(v)\n",
    "        return True\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def verifyPreorder(self, preorder: List[int]) -> bool:\n",
    "        stack = []\n",
    "        min_val = -float('inf')\n",
    "        n = len(preorder)\n",
    "        for i in range(n):\n",
    "            num = preorder[i]\n",
    "            if num <= min_val:\n",
    "                return False\n",
    "            while len(stack) > 0 and num > stack[-1]:\n",
    "                min_val = stack.pop()\n",
    "            stack.append(num)\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def verifyPreorder(self, preorder: List[int]) -> bool:\n",
    "        stack = []\n",
    "        low = float('-inf')\n",
    "        for num in preorder:\n",
    "            if num < low:\n",
    "                return False\n",
    "            while stack and num > stack[-1]:\n",
    "                low = stack.pop()\n",
    "            stack.append(num)\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def verifyPreorder(self, preorder: List[int]) -> bool:\n",
    "        min_val = float('-inf')\n",
    "        k = -1\n",
    "        for num in preorder:\n",
    "            if num < min_val:\n",
    "                return False\n",
    "            while k >= 0 and preorder[k] < num:\n",
    "                min_val = preorder[k]\n",
    "                k -= 1\n",
    "            k += 1\n",
    "            preorder[k] = num\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def verifyPreorder(self, preorder: List[int]) -> bool:\n",
    "        premin = float('-inf')\n",
    "        stack = []\n",
    "        for num in preorder:\n",
    "            if num < premin:\n",
    "                return False\n",
    "            while stack and num > stack[-1]:\n",
    "                premin = stack.pop()\n",
    "            stack.append(num)\n",
    "        return True\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def verifyPreorder(self, preorder: List[int]) -> bool:\n",
    "        stack = []\n",
    "        lower_bound = float('-inf')  # 初始下界设置为无穷小\n",
    "        for value in preorder:\n",
    "            # 如果当前值小于下界，违反了BST性质\n",
    "            if value < lower_bound:\n",
    "                return False\n",
    "            # 更新下界\n",
    "            while stack and stack[-1] < value:\n",
    "                lower_bound = stack.pop()\n",
    "            # 当前值成为下一个右子树节点的下界\n",
    "            stack.append(value)\n",
    "        \n",
    "        # 如果所有元素都被正确处理，意味着它是BST的先序遍历\n",
    "        return True\n",
    "         \n",
    "\n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def verifyPreorder(self, preorder: List[int]) -> bool:\n",
    "        stack=[]\n",
    "        new_min=-inf\n",
    "        for i in range(len(preorder)):\n",
    "            if preorder[i]<new_min: return False\n",
    "            while stack and preorder[i]>stack[-1]:\n",
    "                new_min=stack.pop()\n",
    "            stack.append(preorder[i])\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def verifyPreorder(self, preorder: List[int]) -> bool:\n",
    "        stk1,stk2 = [],-1\n",
    "        for num in preorder:\n",
    "            if num<stk2:\n",
    "                return False\n",
    "            while stk1 and num>stk1[-1]:\n",
    "                stk2=stk1.pop()\n",
    "            stk1.append(num)\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def verifyPreorder(self, preorder: List[int]) -> bool:\n",
    "        test = []\n",
    "        bottom = 0\n",
    "        length = len(preorder)\n",
    "        for i in range(length):\n",
    "            if (preorder[i] < bottom):\n",
    "                return False\n",
    "            while(test and preorder[i]  > test[-1]):\n",
    "                bottom = test.pop()\n",
    "            test.append(preorder[i])\n",
    "            \n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def verifyPreorder(self, preorder: List[int]) -> bool:\n",
    "        stack = []\n",
    "        new_min = float('-inf')  # 初始化下限值\n",
    "        for i in range(len(preorder)):\n",
    "            if preorder[i] < new_min: return False\n",
    "            while stack and preorder[i] > stack[-1]:\n",
    "                new_min = stack.pop()\n",
    "            stack.append(preorder[i])\n",
    "        return True\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def verifyPreorder(self, preorder: List[int]) -> bool:\n",
    "        length = len(preorder)\n",
    "        if length==1:return True\n",
    "\n",
    "        temp = -1 # 用来记录最新pop出来的栈顶元素;可以理解temp为中序排列的【-1】元素\n",
    "        stack = []\n",
    "        for v in preorder:\n",
    "            if temp > v:# 因为v是未来将要被pop的元素（pop的元素就是放到中序列表里的），\n",
    "                        # 如果temp>v，就说明了新中序列表里不是升序的（temp在v前）\n",
    "                return False\n",
    "            while stack and stack[-1]<v:\n",
    "                temp = stack.pop()\n",
    "            stack.append(v)\n",
    "        return True        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def verifyPreorder(self, preorder: List[int]) -> bool:\n",
    "        if len(preorder) <= 2:\n",
    "            return True\n",
    "        stack = []\n",
    "        min_val = -1\n",
    "        for n in preorder:\n",
    "            if n < min_val:\n",
    "                return False\n",
    "            while stack and n > stack[-1]:\n",
    "                min_val = stack.pop()\n",
    "            stack.append(n)\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def verifyPreorder(self, preorder: List[int]) -> bool:\n",
    "        new_min=float('-inf')\n",
    "        stack=[]\n",
    "        for i in range(len(preorder)):\n",
    "            if preorder[i]<new_min: return False\n",
    "            while stack and preorder[i]>stack[-1]:\n",
    "                new_min=stack.pop()\n",
    "            stack.append(preorder[i])\n",
    "        return True\n",
    "\n",
    "#https://leetcode.cn/problems/verify-preorder-sequence-in-binary-search-tree/solutions/72971/python3-tu-jie-by-ml-zimingmeng/\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def verifyPreorder(self, preorder: List[int]) -> bool:\n",
    "        stack = []\n",
    "        new_min = float('-inf')\n",
    "        for i in range(len(preorder)):\n",
    "            if preorder[i] < new_min: return False\n",
    "            while stack and preorder[i] > stack[-1]:\n",
    "                new_min = stack.pop()\n",
    "            stack.append(preorder[i])\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def verifyPreorder(self, preorder: List[int]) -> bool:\n",
    "        minVal, stack = -inf, []\n",
    "        for i, n in enumerate(preorder):\n",
    "            if n < minVal:\n",
    "                return False\n",
    "            while stack and preorder[stack[-1]] < preorder[i]:\n",
    "                minVal = preorder[stack.pop()] \n",
    "            stack.append(i)\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def verifyPreorder(self, preorder: List[int]) -> bool:\n",
    "        stack = []\n",
    "        val = float('-inf')\n",
    "        for i in preorder:\n",
    "            if i < val: return False\n",
    "            while stack and stack[-1] < i:\n",
    "                val = stack.pop()\n",
    "            stack.append(i)\n",
    "        return True\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def verifyPreorder(self, preorder: List[int]) -> bool:\n",
    "\n",
    "        #def dfs(preorder):\n",
    "        # if not preorder or len(preorder) == 0:\n",
    "        #     return True\n",
    "        \n",
    "        # # find ele > root\n",
    "        # right = 1\n",
    "        # for i in range(right, len(preorder)):\n",
    "        #     if preorder[i] > preorder[0]:\n",
    "        #         right = i\n",
    "        #         break\n",
    "        \n",
    "        # for j in range(right, len(preorder)):\n",
    "        #     if preorder[j] < preorder[0]:\n",
    "        #         return False\n",
    "        \n",
    "        # return self.verifyPreorder(preorder[1:right]) and self.verifyPreorder(preorder[right:])\n",
    "        stack = []\n",
    "        min_ = -int(1e9)\n",
    "        for i in range(len(preorder)):\n",
    "            if preorder[i] < min_:\n",
    "                return False\n",
    "            while stack and preorder[i] > stack[-1]:\n",
    "                min_ = stack.pop()\n",
    "            stack.append(preorder[i])\n",
    "        #return dfs(preorder)\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def verifyPreorder(self, preorder: List[int]) -> bool:\n",
    "        stack = []\n",
    "        cur_min = -inf\n",
    "\n",
    "        for x in preorder:\n",
    "            if x < cur_min:\n",
    "                return False\n",
    "            \n",
    "            while stack and x > stack[-1]:\n",
    "                cur_min = stack.pop()\n",
    "\n",
    "            stack.append(x)\n",
    "\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def verifyPreorder(self, preorder: List[int]) -> bool:\n",
    "        stk1,stk2 = [],-1\n",
    "        for num in preorder:\n",
    "            if stk2>0 and num<stk2:\n",
    "                return False\n",
    "            while stk1 and num>stk1[-1]:\n",
    "                tmp=stk1.pop()\n",
    "                if stk2<0 or tmp>stk2:\n",
    "                    stk2=tmp\n",
    "            stk1.append(num)\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def verifyPreorder(self, preorder: List[int]) -> bool:\n",
    "        stack = []\n",
    "        new_min = float(-inf)\n",
    "        for i in range(len(preorder)):\n",
    "            if preorder[i] < new_min:\n",
    "                return False\n",
    "            while stack and preorder[i] > stack[-1]:\n",
    "                new_min = stack.pop()\n",
    "            stack.append(preorder[i])\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def verifyPreorder(self, preorder: List[int]) -> bool:\n",
    "        stack = []\n",
    "        new_min = float('-inf')\n",
    "        for num in preorder:\n",
    "            if num < new_min:\n",
    "                return False\n",
    "            while stack and num > stack[-1]:\n",
    "                new_min = stack.pop()\n",
    "            stack.append(num)\n",
    "        return True\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def verifyPreorder(self, preorder: List[int]) -> bool:\n",
    "        stack = []\n",
    "        new_min = float(\"-inf\")\n",
    "        for i in range(len(preorder)):\n",
    "            if preorder[i] < new_min:\n",
    "                return False\n",
    "            while stack and preorder[i] > stack[-1]:\n",
    "                new_min = stack.pop()\n",
    "            stack.append(preorder[i])\n",
    "        return True\n",
    "        # stack = []\n",
    "        # new_min = float('-inf')  # 初始化下限值\n",
    "        # for i in range(len(preorder)):\n",
    "        #     if preorder[i] < new_min: \n",
    "        #         return False\n",
    "        #     while stack and preorder[i] > stack[-1]:\n",
    "        #         new_min = stack.pop()\n",
    "        #     stack.append(preorder[i])\n",
    "        # return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def verifyPreorder(self, preorder: List[int]) -> bool:\n",
    "        stack = []\n",
    "        min_val = float('-INF')\n",
    "        for val in preorder:\n",
    "            if val < min_val:\n",
    "                return False\n",
    "            while stack and val > stack[-1]:\n",
    "                min_val = stack.pop()\n",
    "            stack.append(val)\n",
    "\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def verifyPreorder(self, preorder: List[int]) -> bool:\n",
    "        stack = []\n",
    "        rootNum = -float('inf')\n",
    "        for val in preorder:\n",
    "            if rootNum > val:\n",
    "                return False\n",
    "            while stack and val > stack[-1]:\n",
    "                rootNum = stack.pop()\n",
    "            stack.append(val)\n",
    "        return True\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def verifyPreorder(self, preorder: List[int]) -> bool:\n",
    "        stack = []\n",
    "        new_min = float('-inf')\n",
    "        for i in range(len(preorder)):\n",
    "            if preorder[i] < new_min: return False\n",
    "            while stack and preorder[i] > stack[-1]:\n",
    "                new_min = stack.pop()\n",
    "            stack.append(preorder[i])\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution(object):\n",
    "    def verifyPreorder(self, preorder):\n",
    "        \"\"\"\n",
    "        :type preorder: List[int]\n",
    "        :rtype: bool\n",
    "        \"\"\"\n",
    "\n",
    "        root_val = -1\n",
    "        stack = []\n",
    "        for v in preorder:\n",
    "            if root_val > v:\n",
    "                return False\n",
    "            \n",
    "            while stack and stack[-1] < v:\n",
    "                root_val = stack[-1]\n",
    "                stack.pop()\n",
    "\n",
    "            stack.append(v)\n",
    "        \n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def verifyPreorder(self, preorder: List[int]) -> bool:\n",
    "        stack = []\n",
    "        new_min = float('-inf')  # 初始化下限值\n",
    "        for i in range(len(preorder)):\n",
    "            if preorder[i] < new_min: return False\n",
    "            while stack and preorder[i] > stack[-1]:\n",
    "                new_min = stack.pop()\n",
    "            stack.append(preorder[i])\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def verifyPreorder(self, preorder):\n",
    "        if not preorder:\n",
    "            return True\n",
    "        stack = []\n",
    "        stack.append(preorder[0])\n",
    "        temp = -1e10\n",
    "        for i in range(1, len(preorder)):\n",
    "            if preorder[i] < temp:\n",
    "                return False\n",
    "            while stack and preorder[i] > stack[-1]:\n",
    "                temp = stack.pop()\n",
    "            stack.append(preorder[i])\n",
    "        return True\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def verifyPreorder(self, preorder: List[int]) -> bool:\n",
    "        stack = []\n",
    "\n",
    "        min_value = float(\"-inf\")\n",
    "\n",
    "        for index, num in enumerate(preorder):\n",
    "            if num < min_value:\n",
    "                return False\n",
    "            \n",
    "        \n",
    "\n",
    "            while stack and num > stack[-1]:\n",
    "                min_value = stack.pop()\n",
    "\n",
    "            stack.append(num)\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def verifyPreorder(self, preorder: List[int]) -> bool:\n",
    "        min_val = -float('inf')\n",
    "        stack = []\n",
    "\n",
    "        for i in preorder:\n",
    "            if i < min_val:\n",
    "                return False\n",
    "            while stack and stack[-1] < i:\n",
    "                min_val = stack.pop()\n",
    "            stack.append(i)\n",
    "        return True\n",
    "            \n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def verifyPreorder(self, preorder: List[int]) -> bool:\n",
    "        stack = deque()\n",
    "        pre = -inf\n",
    "        for val in preorder:\n",
    "            if val < pre:\n",
    "                return False\n",
    "            while stack and val > stack[-1]:\n",
    "                pre = stack.pop()\n",
    "            stack.append(val)\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def verifyPreorder(self, preorder: List[int]) -> bool:\n",
    "        new_min=float('-inf')\n",
    "        stack=[]\n",
    "        for i in range(len(preorder)):\n",
    "            if preorder[i]<new_min: return False\n",
    "            while stack and preorder[i]>stack[-1]:\n",
    "                new_min=stack.pop()\n",
    "            stack.append(preorder[i])\n",
    "        return True\n",
    "\n",
    "#https://leetcode.cn/problems/verify-preorder-sequence-in-binary-search-tree/solutions/72971/python3-tu-jie-by-ml-zimingmeng/\n",
    "\n",
    "#### 局部递减，全局递增\n",
    "#### 后面开始递增的首个元素，要比前面开始递减的那个大\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def verifyPreorder(self, preorder: List[int]) -> bool:\n",
    "        stk1,stk2 = [],[]\n",
    "        for num in preorder:\n",
    "            if stk2 and num<stk2[-1]:\n",
    "                return False\n",
    "            while stk1 and num>stk1[-1]:\n",
    "                tmp=stk1.pop()\n",
    "                if not stk2 or tmp>stk2[-1]:\n",
    "                    stk2.append(tmp)\n",
    "            stk1.append(num)\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def verifyPreorder(self, preorder: List[int]) -> bool:\n",
    "        stk=[]\n",
    "        mi=-10**5\n",
    "        for i in preorder:\n",
    "            if mi>=i:\n",
    "                return False\n",
    "            while len(stk)>0 and stk[-1]<i:\n",
    "                mi=stk.pop()\n",
    "            stk.append(i)\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def verifyPreorder(self, preorder: List[int]) -> bool:\n",
    "        stack = []\n",
    "        new_min = float('-inf')  # 初始化下限值\n",
    "        for i in range(len(preorder)):\n",
    "            if preorder[i] < new_min: return False\n",
    "            while stack and preorder[i] > stack[-1]:\n",
    "                new_min = stack.pop()\n",
    "            stack.append(preorder[i])\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def verifyPreorder(self, preorder: List[int]) -> bool:\n",
    "        stk1,stk2 = [],-1\n",
    "        for num in preorder:\n",
    "            if stk2>0 and num<stk2:\n",
    "                return False\n",
    "            while stk1 and num>stk1[-1]:\n",
    "                tmp=stk1.pop()\n",
    "                if stk2<0 or tmp>stk2:\n",
    "                    stk2=tmp\n",
    "            stk1.append(num)\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def verifyPreorder(self, preorder: List[int]) -> bool:\n",
    "        stack = []\n",
    "        val = float('-inf')\n",
    "        for i in preorder:\n",
    "            if i < val: return False\n",
    "            while stack and stack[-1] < i:\n",
    "                val = stack.pop()\n",
    "            stack.append(i)\n",
    "        return True\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def verifyPreorder(self, preorder: List[int]) -> bool:\n",
    "        new_min = float('-inf')\n",
    "        stack = []\n",
    "        for i in range(len(preorder)):\n",
    "            if preorder[i]<new_min:return False\n",
    "            while stack and stack[-1]<preorder[i]:\n",
    "                new_min = stack.pop()\n",
    "            stack.append(preorder[i])\n",
    "        return True\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def verifyPreorder(self, preorder: List[int]) -> bool:\n",
    "        minval = float('-inf')\n",
    "        stack = []\n",
    "        for i in range(len(preorder)):\n",
    "            if preorder[i] < minval:\n",
    "                return False\n",
    "            while stack and preorder[i] > stack[-1]:\n",
    "                minval = stack.pop()\n",
    "            stack.append(preorder[i])\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def verifyPreorder(self, preorder: List[int]) -> bool:\n",
    "        mono_stack = []\n",
    "        cur_num = float(\"-inf\")\n",
    "        for i in range(len(preorder)):\n",
    "            if preorder[i] < cur_num:\n",
    "                return False\n",
    "            while mono_stack and mono_stack[-1] < preorder[i]:\n",
    "                cur_num = mono_stack.pop()\n",
    "            mono_stack.append(preorder[i])\n",
    "        return True\n",
    "\n",
    "                \n",
    "            \n",
    "\n",
    "            \n",
    "            \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def verifyPreorder(self, preorder: List[int]) -> bool:\n",
    "        cur_min = -1\n",
    "        stack = []\n",
    "        i = 0\n",
    "        for i in range(len(preorder)):\n",
    "            if preorder[i] < cur_min:\n",
    "                return False\n",
    "            while stack and preorder[i] > stack[-1]:\n",
    "                cur_min = stack.pop()\n",
    "            stack.append(preorder[i])\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def verifyPreorder(self, preorder: List[int]) -> bool:\n",
    "        stack = []\n",
    "        new_min = float('-inf')  # 初始化下限值\n",
    "        for i in range(len(preorder)):\n",
    "            if preorder[i] < new_min: return False\n",
    "            while stack and preorder[i] > stack[-1]:\n",
    "                new_min = stack.pop()\n",
    "            stack.append(preorder[i])\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def verifyPreorder(self, preorder: List[int]) -> bool:\n",
    "        curr_min = -inf\n",
    "        stack = []\n",
    "\n",
    "        for x in preorder:\n",
    "            if x < curr_min:\n",
    "                return False\n",
    "\n",
    "            while stack and x > stack[-1]:\n",
    "                curr_min = stack.pop()\n",
    "\n",
    "            stack.append(x)\n",
    "\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def verifyPreorder(self, preorder: List[int]) -> bool:\n",
    "        stack = []\n",
    "        new_min = float('-inf')  # 初始化下限值\n",
    "        for i in range(len(preorder)):\n",
    "            if preorder[i] < new_min: return False\n",
    "            while stack and preorder[i] > stack[-1]:\n",
    "                new_min = stack.pop()\n",
    "            stack.append(preorder[i])\n",
    "        return True\n",
    "\n",
    "# 作者：腐烂的橘子\n",
    "# 链接：https://leetcode.cn/problems/verify-preorder-sequence-in-binary-search-tree/solutions/72971/python3-tu-jie-by-ml-zimingmeng/\n",
    "# 来源：力扣（LeetCode）\n",
    "# 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def verifyPreorder(self, preorder: List[int]) -> bool:\n",
    "        \"\"\"\n",
    "        整体走势应该是递增的\n",
    "        二叉搜索树，一定是整体左子树是递减，如果遇到非递减应该是在右子树上，弹出栈内元素即可\n",
    "        站内元素需要比当前元素小\n",
    "        \"\"\"\n",
    "        min_num = float('-inf')\n",
    "        stack = [] \n",
    "        for i in range(0,len(preorder)):\n",
    "            if preorder[i]< min_num: return False \n",
    "            while stack and preorder[i]>stack[-1]:\n",
    "                min_num = stack.pop()\n",
    "\n",
    "            stack.append(preorder[i])\n",
    "        return True\n",
    "        \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# class Solution:\n",
    "#     def verifyPreorder(self, preorder: List[int]) -> bool:\n",
    "#         l,r = 1,len(preorder)-1\n",
    "#         if r <= 1:return True\n",
    "#         while 0 <= l < len(preorder) and preorder[0] > preorder[l]:\n",
    "#             l += 1\n",
    "#         while 0 <= r < len(preorder) and preorder[0] < preorder[r]:\n",
    "#             r -= 1\n",
    "#         if l - r != 1:\n",
    "#             return False\n",
    "#         return self.verifyPreorder(preorder[1:l]) and self.verifyPreorder(preorder[l:])\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def verifyPreorder(self, preorder: List[int]) -> bool:\n",
    "        stack = []\n",
    "        new_min = float('-inf')  # 初始化下限值\n",
    "        for i in range(len(preorder)):\n",
    "            if preorder[i] < new_min:\n",
    "                return False\n",
    "            while stack and preorder[i] > stack[-1]:\n",
    "                new_min = stack.pop()\n",
    "            stack.append(preorder[i])\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def verifyPreorder(self, preorder: List[int]) -> bool:\n",
    "        s = []\n",
    "        n = len(preorder)\n",
    "        pre = -inf \n",
    "        for i in range(n):\n",
    "            if preorder[i] < pre:\n",
    "                return False\n",
    "            while s and preorder[i] > s[-1]:\n",
    "                pre = s.pop()\n",
    "            s.append(preorder[i])\n",
    "        return True "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def verifyPreorder(self, preorder: List[int]) -> bool:\n",
    "        n = len(preorder)\n",
    "        if n <= 2:\n",
    "            return True\n",
    "        \n",
    "        min_val, stack = -float(\"inf\"), []\n",
    "        for i in range(n):\n",
    "            val = preorder[i]\n",
    "            if val <= min_val:\n",
    "                return False\n",
    "            while stack and val > stack[-1]:\n",
    "                min_val = stack.pop()\n",
    "            stack.append(val)\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def verifyPreorder(self, preorder: List[int]) -> bool:\n",
    "        stack=[]\n",
    "        new_min=-inf\n",
    "        for i in range(len(preorder)):\n",
    "            if preorder[i]<new_min: return False\n",
    "            while stack and preorder[i]>stack[-1]:\n",
    "                new_min=stack.pop()\n",
    "            stack.append(preorder[i])\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def verifyPreorder(self, preorder: List[int]) -> bool:\n",
    "        stk1,stk2 = [],[]\n",
    "        for num in preorder:\n",
    "            if stk2 and num<stk2[-1]:\n",
    "                return False\n",
    "            while stk1 and num>stk1[-1]:\n",
    "                tmp=stk1.pop()\n",
    "                if not stk2 or tmp>stk2[-1]:\n",
    "                    stk2.append(tmp)\n",
    "            stk1.append(num)\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def verifyPreorder(self, preorder):\n",
    "        if not preorder:\n",
    "            return True\n",
    "        stack = []\n",
    "        stack.append(preorder[0])\n",
    "        temp = -1e10\n",
    "        for i in range(1, len(preorder)):\n",
    "            if preorder[i] < temp:\n",
    "                return False\n",
    "            while stack and preorder[i] > stack[-1]:\n",
    "                temp = stack.pop()\n",
    "            stack.append(preorder[i])\n",
    "        return True\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import deque\n",
    "class Solution:\n",
    "    def verifyPreorder(self, preorder: List[int]) -> bool:\n",
    "        stack = deque()\n",
    "        i = 0\n",
    "        min_num = -float('inf')\n",
    "        while i < len(preorder):\n",
    "            if preorder[i] < min_num:\n",
    "                return False\n",
    "            if not stack:\n",
    "                stack.append(preorder[i])\n",
    "                i += 1\n",
    "                continue\n",
    "            if stack[-1] > preorder[i]:\n",
    "                stack.append(preorder[i])\n",
    "                i += 1\n",
    "            else:\n",
    "                min_num = stack.pop()\n",
    "        return True\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def verifyPreorder(self, preorder: List[int]) -> bool:\n",
    "        cur_min = -inf\n",
    "        stack = []\n",
    "\n",
    "        for i, v in enumerate(preorder):\n",
    "            if v < cur_min:\n",
    "                return False\n",
    "\n",
    "            while stack and v > stack[-1][0]:\n",
    "                cur_min, _ = stack.pop()\n",
    "\n",
    "            stack.append((v, i))\n",
    "            \n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    #8000层递归，每层递归一次，实际上只有左右分叉的二叉树需要检查，即每次在检查可以跳过只有一个子节点的中间节点\n",
    "    #若单增，后再减，则可跳过中间，只有右子树\n",
    "    #若单减，只有左子树\n",
    "    def verifyPreorder(self, preorder: List[int]) -> bool:\n",
    "        def check(preorder):\n",
    "            if len(preorder)<=2:\n",
    "                return True\n",
    "            right=len(preorder)\n",
    "            for i in range(1,len(preorder)):\n",
    "                if preorder[i]>preorder[0]:\n",
    "                    right=i\n",
    "                    break\n",
    "            for i in range(right,len(preorder)):\n",
    "                if preorder[i]<preorder[0]:\n",
    "                    return False\n",
    "            for i in range(1,right):\n",
    "                if preorder[i]>preorder[0]:\n",
    "                    return False\n",
    "            left=right\n",
    "            if right==1:\n",
    "                for i in range(right+1,len(preorder)):\n",
    "                    if preorder[i]>preorder[i-1]:\n",
    "                        right=i-1\n",
    "                    else:\n",
    "                        break\n",
    "            left_start=1\n",
    "            for i in range(2,left):\n",
    "                if preorder[i]<preorder[i-1]:\n",
    "                    left_start=i-1\n",
    "                else:\n",
    "                    break\n",
    "            return check(preorder[left_start:left]) and check(preorder[right:])\n",
    "        return check(preorder)"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
